package thired.class08_tree;

import java.util.Stack;

public class Class01_UnRecursiveTraversalBT {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }

    public static void pre(Node root){
        System.out.print("pre-order: ");
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
           Node cur = stack.pop();
            System.out.print(cur.value + " ");
           if(cur.right != null){
               stack.push(cur.right);
           }
           if(cur.left != null){
               stack.push(cur.left);
           }
        }
        System.out.println();
    }

    public static void in(Node root){
        System.out.print("in-order: ");
        Stack<Node> stack = new Stack<>();
        while(!stack.isEmpty() || root != null){
            if(root != null){
                stack.push(root);
                root = root.left;
            }else{
                root = stack.pop();
                System.out.print(root.value + " ");
                root = root.right;
            }
        }
        System.out.println();
    }

    public static void pos(Node root){
        System.out.print("pos-order: ");
        Stack<Node> stack = new Stack<>();
        Stack<Integer> stack1 = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            stack1.push(cur.value);
            if(cur.left != null){
                stack.push(cur.left);
            }
            if(cur.right != null){
                stack.push(cur.right);
            }
        }
        while (!stack1.isEmpty()){
            System.out.print(stack1.pop() + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        pre(head);
        System.out.println("========");
        in(head);
        System.out.println("========");
        pos(head);
        System.out.println("========");
//        pos2(head);
//        System.out.println("========");
    }

}
